package io.github.hadyang.leetcode.offer;

import io.github.hadyang.leetcode.ListNode;
import org.junit.Test;

/** @author haoyang.shi */
public class MergeSortLink {

  @Test
  public void test() {
    ListNode head4 = new ListNode(1);
    ListNode head5 = new ListNode(3);
    ListNode head6 = new ListNode(4);
    head4.next = head5;
    head5.next = head6;

    ListNode res = Merge(null, head4);

    while (res != null) {
      System.out.print(res.val);
      res = res.next;
    }
  }

  public ListNode Merge(ListNode list1, ListNode list2) {
    ListNode head = new ListNode(-1);
    ListNode cursor = head;

    while (list1 != null || list2 != null) {
      if (list1 == null) {
        while (list2 != null) {
          cursor.next = list2;
          cursor = cursor.next;
          list2 = list2.next;
        }

        continue;
      }

      if (list2 == null) {
        while (list1 != null) {
          cursor.next = list1;
          cursor = cursor.next;
          list1 = list1.next;
        }

        continue;
      }

      if (list1.val < list2.val) {
        cursor.next = list1;
        cursor = cursor.next;

        list1 = list1.next;
      } else {
        cursor.next = list2;
        cursor = cursor.next;

        list2 = list2.next;
      }
    }

    return head.next;
  }
}
